package sort.insertsort;

import sort.generator.ArrayGenerator;
import sort.helper.SortingHelper;

import java.util.Arrays;

/**
 * @author XY
 * @version 1.0
 * @date 2021/8/17 14:50
 * @Description 插入排序
 */
public class InsertSort {

    private InsertSort(){}

    public static void main(String[] args) {
        int[] dataSize = {10000,100000};
        for (int n : dataSize) {
            Integer[] integers = ArrayGenerator.generateRandomArray(n, n);
            Integer[] integers1 = Arrays.copyOf(integers, integers.length);
            SortingHelper.sortTest("InsertSortBetter",integers);
            SortingHelper.sortTest("InsertSort",integers1);
        }
    }

    public static <E extends Comparable<E>> void insertSort(E[] arr){
        // arr[0..i)是有序的，arr[i...n)是无序的，这是该排序算法的循环不变量
        for (int i = 1; i < arr.length; i++) {
//            for (int j = i; j>0; j--) {
//                if(arr[j].compareTo(arr[j-1])<0){
//                    E temp = arr[j];
//                    arr[j] = arr[j-1];
//                    arr[j-1]=temp;
//                }else{
//                    //如果发现当前元素已经大于上一个元素，说明这个元素不需要交换位置，因为这个元素之前的都是排好序的
//                    break;
//                }
//            }
            for (int j = i; j>0&&arr[j].compareTo(arr[j-1])<0; j--) {
                E temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1]=temp;
            }
        }
    }

    //提供给归并排序的插入排序
    public static <E extends Comparable<E>> void insertSort(E[] arr,int l,int r){
        // arr[0..i)是有序的，arr[i...n)是无序的，这是该排序算法的循环不变量
        for (int i = l; i <= r; i++) {
            E temp1 = arr[i];
            int j;
            for (j = i; j > l && temp1.compareTo(arr[j-1])<0; j--) {
                arr[j]=arr[j-1];
            }
            arr[j]=temp1;
        }
    }

    //优化插入排序 ，使得程序不需要做交换操作，仅仅只做移动操作即可达到效果
    public static <E extends Comparable<E>> void insertSortBetter(E[] arr){
        // arr[0..i)是有序的，arr[i...n)是无序的，这是该排序算法的循环不变量
        for (int i = 1; i < arr.length; i++) {
            E temp1 = arr[i];
            int j;
            for (j = i; j>0&&temp1.compareTo(arr[j-1])<0; j--) {
                arr[j]=arr[j-1];
            }
            arr[j]=temp1;
        }
    }
}
